package codingforgreat.class04;
// 本题测试链接 : https://leetcode.com/problems/interleaving-string/
public class Class07_InterleavingString {
    public boolean isInterleave(String s1, String s2, String s3) {
        if (s1 == null || s2 == null || s3 == null) {
            return false;
        }
        char[] str1 = s1.toCharArray();
        char[] str2 = s2.toCharArray();
        char[] str3 = s3.toCharArray();
        if(str1.length + str2.length != str3.length){
            return false;
        }
        int N = s1.length();
        int M = s2.length();
        boolean[][] dp = new boolean[N + 1][M + 1];
        dp[0][0] = true;
        for (int i = 1; i <= N; i++) {
            if(str1[i - 1] != str3[i - 1]){
                break;
            }
            dp[i][0] = true;
        }
        for (int i = 1; i <= M; i++) {
            if(str2[i - 1] != str3[i - 1]){
                break;
            }
            dp[0][i] = true;
        }

        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= M; j++) {
                dp[i][j] = (dp[i - 1][j] && str1[i - 1] == str3[i + j - 1]) ||
                        (dp[i][j - 1] && str2[j - 1] == str3[i + j - 1]);
            }

        }
        return dp[N][M];
    }
}
